#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10; // 定义最大节点数

int t, n, m;            // t:测试用例数, n:节点数, m:边数
int p[N], sz[N], d[N];  // p:并查集父数组, sz:连通块环数, d:BFS距离数组
vector<int> g[N];       // 邻接表存储图

// 并查集查找函数（带路径压缩）
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]); // 递归压缩路径
    return p[x];
}

void solve() {
    cin >> n >> m;

    // 初始化数据结构
    for (int i = 1; i <= n; i++) {
        g[i].clear();    // 清空邻接表
        p[i] = i;        // 并查集初始化：每个节点是自己的父节点
        d[i] = -1;       // 距离数组初始化为未访问状态
        sz[i] = 0;       // 每个连通块的环数初始化为0
    }

    int st = -1, ed = -1; // 记录环的两个端点（用于BFS）

    // 处理每条边
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b); // 添加双向边到邻接表
        g[b].push_back(a);

        int fa = find(a), fb = find(b);
        if (fa != fb) {
            // 情况1：两个节点属于不同连通块
            p[fa] = fb;            // 合并连通块
            sz[fb] += sz[fa];      // 累加环的数量（sz[fa]可能是0或1）
        } else {
            // 情况2：两个节点属于同一连通块，形成新环
            sz[fa]++;              // 当前连通块的环数+1
            st = a; ed = b;        // 记录环的端点（后续BFS用）
        }
    }

    // 统计符合条件的章鱼子图数量（sz[i]==1的连通块）
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i && sz[i] == 1) { // 只统计根节点且环数为1的连通块
            ans++;
        }
    }

    // 判断是否只有一个章鱼子图
    if (ans != 1) {
        cout << "No " << ans << endl;
        return;
    }

    // BFS计算环的大小（从st出发，避开st-ed边）
    queue<int> q;
    q.push(st);
    d[st] = 0; // 起点到自身的距离为0

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 遍历u的所有邻居
        for (int v : g[u]) {
            // 跳过构成环的边（st和ed之间的边）
            if ((u == st && v == ed) || (u == ed && v == st)) continue;

            if (d[v] == -1) { // 未被访问过
                d[v] = d[u] + 1; // 更新距离
                q.push(v);     // 加入队列继续搜索
            }
        }
    }

    // 输出结果：环的大小 = 最短路径边数 + 1
    cout << "Yes " << d[ed] + 1 << endl;

}

int main() {
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
